﻿namespace Leetcode.N1392;

public class Solution
{
    public string LongestPrefix(string s)
    {
        int nextIndex = 0;
        int fromIndex = 1;
        for (int i = 1; i < s.Length; i++)
        {
            if (s[i] == s[nextIndex])
            {
                nextIndex++;
            }
            else
            {
                var ii = i;
                for (int j = nextIndex; j > 0; j--)
                {
                    if (ii <= fromIndex)
                    {
                        nextIndex = 0;
                        break;
                    }

                    if (s[ii] == s[j - 1])
                    {
                        ii--;
                        continue;
                    }
                    ii = i;
                    nextIndex = j - 1;
                }

                fromIndex = ii;
            }
        }
        return (nextIndex > 0) ? s.Substring(0, nextIndex) : "";
    }
}
